package leetcode.graph.common;

import java.util.*;

public class GraphUtils {

    /**
     * 给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。
     * <p>
     * 岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。
     * <p>
     * 你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。
     * <p>
     * 返回必须翻转的 0 的最小数目。
     * <p>
     * n == grid.length == grid[i].length
     * 2 <= n <= 100
     * grid[i][j] 为 0 或 1
     * grid 中恰有两个岛
     *
     * @param grid
     * @return
     */
    public static int shortestBridge(int[][] grid) {

        // grid n * n
        // 宽度 = 高度
        int n = grid.length;

        Queue<int[]> queue = new LinkedList<>();

        boolean findFlag = false;
        // 找到第一个岛的第一个位置
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    grid[i][j] = -1;
                    queue.add(newNode(i, j));
                    findFlag = true;
                    break;
                }
            }
            if(findFlag){
                break;
            }
        }

        List<int[]> dir = new ArrayList<>();
        dir.add(newNode(0, 1));
        dir.add(newNode(0, -1));
        dir.add(newNode(1, 0));
        dir.add(newNode(-1, 0));

        List<int[]> isLand = new ArrayList<>();
        // 找到第一个岛的所有元素
        while (queue.size() > 0) {
            // 出队, 执行某些操作
            int[] head = queue.poll();
            int x = head[0];
            int y = head[1];
            // 加入第一个小岛的元素集合
            isLand.add(head);
            for (int[] ints : dir) {
                int newX = x + ints[0];
                int newY = y + ints[1];
                if (isOK(newX, n) && isOK(newY, n)) {
                    // 否则在此处的判断会导致重复添加队列中的元素
                    if (grid[newX][newY] == 1) {
                        // 必须在入队的时候就标记被访问过
                        grid[newX][newY] = -1;
                        queue.add(newNode(newX, newY));
                    }
                }
            }
        }

        // 准备队列
        queue.clear();
        queue.addAll(isLand);

        // 以第一个岛为第一层向外扩张
        int step = 0;
        while (queue.size() > 0) {
            // 当前层的大小
            int levelSize = queue.size();
            // 遍历当前层的所有节点
            for (int i = 0; i < levelSize; i++) {
                // 当前层节点挨个出队
                int[] head = queue.poll();
                int x = head[0];
                int y = head[1];
                // 遍历当前节点的四周节点
                for (int[] ints : dir) {
                    int newX = x + ints[0];
                    int newY = y + ints[1];
                    if (isOK(newX, n) && isOK(newY, n)) {
                        // 遍历过程中存在某个节点为1, 说明找到了另一个小岛, 返回结果
                        if (grid[newX][newY] == 1) {
                            return step;
                        }
                        if (grid[newX][newY] == 0) {
                            grid[newX][newY] = -1;
                            // 下一层节点入队
                            queue.add(newNode(newX, newY));
                        }
                    }
                }
            }
            step++;
        }
        // -1表示不可达, 不存在第二个小岛
        return -1;
    }

    private static int[] newNode(int newX, int newY) {
        return new int[]{newX, newY};
    }

    private static boolean isOK(int pos, int max) {
        // 索引在 0-(n-1)之间为有效
        return pos >= 0 && pos <= max - 1;
    }

    public static int countComponents(int n, int[][] edges) {
        // graph中每一个List元素都表示一个节点,以及该节点所连接到的所有其他节点
        // 就是邻接表的存储方式
        List<List<Integer>> graph = new ArrayList<>();
        boolean[] visited = new boolean[n];
        for(int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for(int[] edge : edges){
            int u = edge[0], v = edge[1];
            graph.get(u).add(v); // 无向图边 (u,v)
            graph.get(v).add(u); // 无向图边 (v,u)
        }
        int count = 0;
        // 节点值从 0 到 n
        for(int u = 0; u < n; u++){
            if(!visited[u]) {
                count++; // 只要顶点 u 此时尚未被访问，说明它不再此前的链路(连通分量)中，以它为新的连通分量起点
                dfs(u, visited, graph);
            }
        }
        return count;
    }

    private static void dfs(int u, boolean[] visited, List<List<Integer>> graph){
        visited[u] = true;
        for(int v : graph.get(u)) {
            // v没有被访问过,进入v节点
            if(!visited[v]) dfs(v, visited, graph);
        }
    }

    public static int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        // 邻接表的存储方式
        // 红蓝色的图各需要一个邻接表
        List<Integer>[][] next = new List[2][n];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                next[i][j] = new ArrayList<>();
            }
        }
        for (int[] edge : redEdges) {
            next[0][edge[0]].add(edge[1]);
        }
        for (int[] edge : blueEdges) {
            next[1][edge[0]].add(edge[1]);
        }
        int[][] dist = new int[2][n]; // 两种类型的颜色最短路径的长度
        for (int i = 0; i < 2; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        Queue<int[]> queue = new ArrayDeque<>();
        dist[0][0] = 0;
        dist[1][0] = 0;
        queue.offer(new int[]{0, 0});
        queue.offer(new int[]{0, 1});
        while (!queue.isEmpty()) {
            int[] pair = queue.poll();
            int x = pair[0], t = pair[1];
            for (int y : next[1 - t][x]) {
                if (dist[1 - t][y] != Integer.MAX_VALUE) {
                    continue;
                }
                dist[1 - t][y] = dist[t][x] + 1;
                queue.offer(new int[]{y, 1 - t});
            }
        }
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            answer[i] = Math.min(dist[0][i], dist[1][i]);
            if (answer[i] == Integer.MAX_VALUE) {
                answer[i] = -1;
            }
        }
        return answer;
    }
}
